package com.datastructures2.graph.有向图;

import com.datastructures2.graph.最短路径.DirectedEdge;
import com.datastructures2.graph.最短路径.EdgeWeightedDigraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.KosarajuSharirSCC;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;

/**
 * 有向图中基于深度优先搜索的顶点排序
 * @author MaoLin Wang
 * @date 2020/2/2214:55
 */
public class DepthFirstOrder {
    private boolean[]marked;
    /**
     * 所有顶点的前序遍历(递归调用前加入队列)
     */
    private Queue<Integer> pre;
    /**
     * 所有顶点的后序遍历(递归调用后加入队列)
     */
    private Queue<Integer> post;
    /**
     * 所有顶点的逆后序遍历(递归调用后压入栈)
     */
    private Stack<Integer> reversePost;

    public DepthFirstOrder(Digraph digraph) {

        pre=new Queue<>();
        post=new Queue<>();
        reversePost=new Stack<>();
        marked=new boolean[digraph.V()];

        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v]){
                dfs(digraph,v);
            }
        }


    }
    public DepthFirstOrder(EdgeWeightedDigraph digraph){
        pre=new Queue<>();
        post=new Queue<>();
        reversePost=new Stack<>();
        marked=new boolean[digraph.V()];
        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v]){
                dfs(digraph,v);
            }
        }
    }
    private void dfs(EdgeWeightedDigraph digraph,int v){
        pre.enqueue(v);
        marked[v]=true;
        for (DirectedEdge edge:digraph.adj(v)){
            if (!marked[edge.to()]){
                dfs(digraph,edge.to());
            }
        }

        post.enqueue(v);
        reversePost.push(v);
    }
    private void dfs(Digraph digraph, int v) {
        System.out.println("dfs("+v+")");

        pre.enqueue(v);
        marked[v]=true;
        for (int w: digraph.adj(v)){
            if (!marked[w]){
                dfs(digraph,w);
            }
        }
        System.out.println(v+"完成");

        post.enqueue(v);
        reversePost.push(v);
    }

    public Iterable<Integer>pre(){
        return pre;
    }

    public Queue<Integer>post(){
        return post;
    }
    public Iterable<Integer>reversePost(){
        return reversePost;
    }

    public static void main(String[] args) {
        Digraph digraph = new Digraph(13);
        digraph.addEdge(0,5);
        digraph.addEdge(0,1);
        digraph.addEdge(0,6);
        digraph.addEdge(2,0);
        digraph.addEdge(2,3);
        digraph.addEdge(3,5);
        digraph.addEdge(5,4);
        digraph.addEdge(6,4);
        digraph.addEdge(6,9);
        digraph.addEdge(7,6);
        digraph.addEdge(8,7);
        digraph.addEdge(9,10);
        digraph.addEdge(9,11);
        digraph.addEdge(9,12);
        digraph.addEdge(11,12);
        DepthFirstOrder depthFirstOrder = new DepthFirstOrder(digraph);
        Stack<Integer> reversePost = depthFirstOrder.reversePost;
        while (!reversePost.isEmpty())
        {
            System.out.println(reversePost.pop());
        }


    }
}
